package algo.A04_快速排序和归并排序;

import util.ArrayUtil;

/**
 * 奇数在左：
 * 输入一个整数数组，调整数组中数字的顺序，
 * 使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
 * 要求时间复杂度为O(n)
 */
public class T01_奇数在左_双指针法 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 0, 100);
        ArrayUtil.print(arr);
        solution(arr);
        ArrayUtil.print(arr);
    }

    /**
     * 解题思路：
     * 没有规定有序，可以用快速排序的思想，使用两个指针，
     * 左边扫偶数，右边扫奇数，当左边指向偶数右边指向奇数时，两数对换
     * 直到左指针与右指针重合
     */
    private static void solution(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while(left < right){
            while (arr[left] % 2 != 0){
                left++;
            }
            while (arr[right] % 2 == 0){
                right--;
            }
            ArrayUtil.swap(arr,left++,right--);
        }
    }
}
